package com.tys.algorithm.advanced.test.class18;

/**
 * 机器人走到指定位置的方法有多少种？
 * 假设有排成一行的N个位置，记为1-N，N一定大于或等于2
 * 开始时机器人在其中的M位置上（M一定是1-N中的一个）
 * 如果机器人来到1位置，那么下一步只能往右来到2位置
 * 如果机器人来到N位置，那么下一步只能往左来到N-1位置
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走
 * 规定机器人必须走K步，最终能来到P位置（P也是1-N中的一个）方法有多少种
 * 给定四个参数N,M,K,P返回方法数
 */
public class Code01_RobotWalk {

    /**
     * 方法1：
     * N: 一共多少位置
     * start：机器人开始位置在那
     * aim：机器人目标位置
     * K：总共走几步
     * 返回有几种方法到达目标位置
     */
    public static int ways1(int N, int start, int aim, int K) {
        //判断边界条件
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(start, K, aim, N);
    }

    // cur: 机器人当前来到的位置是cur，
    // rest: 机器人还有rest步需要去走，
    // aim: 最终的目标是aim，
    // N: 有哪些位置？1~N
    // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
    //cur 和 rest 确定后返回值就固定了
    public static int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) { // 如果已经不需要走了，走完了！
            //cur在aim位置说明发现了一种方法
            return cur == aim ? 1 : 0;
        }
        // 现在的位置在1位置，必须去2，向右走(cur, rest)
        if (cur == 1) { // 1 -> 2
            //从2位置开始的方法数量
            return process1(2, rest - 1, aim, N);
        }
        // 现在在N位置，需要走到N-1位置，向左走(cur, rest)
        if (cur == N) { // N-1 <- N
            //从N-1位置开始的方法数量
            return process1(N - 1, rest - 1, aim, N);
        }
        //在中间位置：可以向左，可以向右
        //向左的方法数+向右的方法数 (cur, rest)
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }

    //方法2：傻缓存法
    // cur 和 rest 确定后返回值就固定了
    public static int ways2(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }

        //二维数组长度:(N+1)*(K+1)
        int[][] dp = new int[N + 1][K + 1];
        //初始化dp数组：都设置为-1
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        // dp就是缓存表
        // dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
        // dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
        // N+1 * K+1
        return process2(start, K, aim, N, dp);
    }

    // cur 范围: 1 ~ N
    // rest 范围：0 ~ K
    public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 之前没算过！
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = process2(2, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
        }
        //结果缓存
        dp[cur][rest] = ans;
        return ans;

    }

    //方法3：会撞墙的杨辉三角形
    // N：多少位置
    // start: 起始位置
    // rest: 机器人还有rest步需要去走，
    // aim: 最终的目标是aim，
    // K：总共走几步
    public static int ways3(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        //缓存数组
        int[][] dp = new int[N + 1][K + 1];
        //首先填充第0列：找到base case
        dp[aim][0] = 1;
        //从第1列开始填充
        for (int rest = 1; rest <= K; rest++) {
            //第一行：在1位置时，依赖左下：2位置的rest-1
            dp[1][rest] = dp[2][rest - 1];
            //中间行：从第2行开始
            for (int cur = 2; cur < N; cur++) {
                //左上：依赖cur-1位置的rest-1
                //左下：依赖cur+1位置的rest-1
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            //最后一行：N位置，依赖左上：N-1位置的rest-1
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        //最终要的结果是start,k的结果
        return dp[start][K];
    }

    public static void main(String[] args) {
        System.out.println(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }

}
